# @Time: 2022/3/23 11:10
# @Author: HeYuanqing
# @Reference: https://www.cnblogs.com/devymex/archive/2010/08/19/1803885.html
import math


# 判断两数是否相等
def equal(f1, f2):
    if abs(f1 - f2) < math.e * pow(10, -5):
        return True
    else:
        return False


# 判断两点是否重合
def pointEqual(p1, p2):
    if equal(p1[0], p2[0]) & equal(p1[1], p2[1]):
        return True
    else:
        return False


# 判断坐标顺序
def pointOrder(p1, p2):
    if p1[0] > p2[0]:
        return True
    else:
        if equal(p1[0], p2[0]):
            if p1[1] > p2[1]:
                return True
        else:
            return False


# 计算量向量外积
def vectorCross(p1, p2):
    return p1[0] * p2[1] - p1[1] * p2[0]


# 判定两线段位置关系，并求出交点(如果存在)。返回值列举如下：
# [有重合] 完全重合(6)，1个端点重合且共线(5)，部分重合(4)
# [无重合] 两端点相交(3)，交于线上(2)，正交(1)，无交(0)，参数错误(-1)
def Intersection(p1, p2, p3, p4, intPoint):
    # 保证参数p1!=p2，p3!=p4
    if pointEqual(p1, p2) | pointEqual(p3, p4):
        return -1  # 返回-1代表至少有一条线段首尾重合，不能构成线段

    # 为方便运算，保证各线段的起点在前，终点在后。
    if pointOrder(p1, p2):
        p1, p2 = p2, p1
    if pointOrder(p3, p4):
        p3, p4 = p4, p3

    # 判定两线段是否完全重合
    if pointEqual(p1, p3) & pointEqual(p2, p4):
        return 6
    # 求出两线段构成的向量

    v1 = [p2[0] - p1[0], p2[1] - p1[1]]
    v2 = [p4[0] - p3[0], p4[1] - p3[1]]
    # 求两向量外积，平行时外积为0
    Corss = vectorCross(v1, v2)
    # 如果起点重合
    if pointEqual(p1, p3):
        intPoint[0] = p1[0]
        intPoint[1] = p1[1]
        # 起点重合且共线(平行)返回5；不平行则交于端点，返回3
        if equal(Corss, 0):
            return 5
        else:
            return 3
    # 如果终点重合
    if pointEqual(p2, p4):

        intPoint[0] = p2[0]
        intPoint[1] = p2[1]
        # 终点重合且共线(平行) 返回5；不平行则交于端点，返回3
        if equal(Corss, 0):
            return 5
        else:
            return 3
    # 如果两线端首尾相连
    if pointEqual(p1, p4):
        intPoint[0] = p1[0]
        intPoint[1] = p1[1]
        return 3
    if pointEqual(p2, p3):
        intPoint[0] = p2[0]
        intPoint[1] = p2[1]
        return 3
    # 经过以上判断，首尾点相重的情况都被排除了
    # 将线段按起点坐标排序。若线段1的起点较大，则将两线段交换
    if pointOrder(p1, p3):
        p1, p3 = p3, p1
        p2, p4 = p4, p2
        v1, v2 = v2, v1
        Corss = vectorCross(v1, v2)

    # 处理两线段平行的情况
    if equal(Corss, 0):
        # 做向量v1(p1, p2)和vs(p1, p3)的外积，判定是否共线
        vs = [p3[0] - p1[0], p3[1] - p1[1]];
        # 外积为0则两平行线段共线，下面判定是否有重合部分
        if equal(vectorCross(v1, vs), 0):
            # 前一条线的终点大于后一条线的起点，则判定存在重合
            if pointOrder(p2, p3):
                intPoint[0] = p3[0]
                intPoint[1] = p3[1]
                return 4  # 返回值4代表线段部分重合

        # 若三点不共线，则这两条平行线段必不共线。
        # 不共线或共线但无重合的平行线均无交点
        return 0

    # 以下为不平行的情况，先进行快速排斥试验
    # x坐标已有序，可直接比较。y坐标要先求两线段的最大和最小值
    ymax1 = p1[1] * 1.0
    ymin1 = p2[1] * 1.0
    ymax2 = p3[1] * 1.0
    ymin2 = p4[1] * 1.0
    if ymax1 < ymin1:
        ymax1, ymin1 = ymin1, ymax1
    if ymax2 < ymin2:
        ymax2, ymin2 = ymin2, ymax2
    # 如果以两线段为对角线的矩形不相交，则无交点

    if p1[0] > p4[0]:
        return 0
    elif p2[0] < p3[0]:
        return 0
    elif ymax1 < ymin2:
        return 0
    elif ymin1 > ymax2:
        return 0
    # 下面进行跨立试验
    vs1 = [p1[0] - p3[0], p1[1] - p3[1]]
    vs2 = [p2[0] - p3[0], p2[1] - p3[1]]
    vt1 = [p3[0] - p1[0], p3[1] - p1[1]]
    vt2 = [p4[0] - p1[0], p4[1] - p1[1]]

    s1v2 = vectorCross(vs1, v2)
    s2v2 = vectorCross(vs2, v2)
    t1v1 = vectorCross(vt1, v1)
    t2v1 = vectorCross(vt2, v1)
    # 根据外积结果判定否交于线上
    if equal(s1v2, 0) & pointOrder(p4, p1) & pointOrder(p1, p3):
        intPoint[0] = p1[0]
        intPoint[1] = p1[1]
        return 2

    if equal(s2v2, 0) & pointOrder(p4, p2) & pointOrder(p2, p3):
        intPoint[0] = p2[0]
        intPoint[1] = p2[1]
        return 2

    if equal(t1v1, 0) & pointOrder(p2, p3) & pointOrder(p3, p1):
        intPoint[0] = p3[0]
        intPoint[1] = p3[1]
        return 2
    if equal(t2v1, 0) & pointOrder(p2, p4) & pointOrder(p4, p1):
        intPoint[0] = p4[0]
        intPoint[1] = p4[1]
        return 2

    # 未交于线上，则判定是否相交

    if s1v2 * s2v2 > 0:
        return 0
    elif t1v1 * t2v1 > 0:
        return 0

    # 以下为相交的情况，算法详见文档
    # 计算二阶行列式的两个常数项

    ConA = p1[0] * v1[1] - p1[1] * v1[0]

    ConB = p3[0] * v2[1] - p3[1] * v2[0]
    # 计算行列式D1和D2的值，除以系数行列式的值，得到交点坐标
    intPoint[0] = (ConB * v1[0] - ConA * v2[0]) / Corss
    intPoint[1] = (ConB * v1[1] - ConA * v2[1]) / Corss
    # 正交返回1
    return 1


if __name__ == '__main__':
    # 判定两线段位置关系，并求出交点(如果存在)。返回值列举如下：
    # [有重合] 完全重合(6)，一个端点重合且共线(5)，部分重合(4)
    # [无重合] 两端点相交(3)，一端点在线上相交(2)，相交(1)，无交(0)，参数错误(-1)
    intPoint = [float("inf"), float("inf")]  # 存储交点坐标
    nr = Intersection([0, 0], [10, 0], [10, 0], [18, 6], intPoint)  # 参数为两线段的顶点坐标和交点坐标数组
    if nr == -1:
        print("-1:参数错误")
    elif nr == 0:
        print("0:无交")
    elif nr == 1:
        print("1:相交")
    elif nr == 2:
        print("2:一端点在线上相交")
    elif nr == 3:
        print("3:两端点相交")
    elif nr == 4:
        print("4:部分重合")
    elif nr == 5:
        print("5:1个端点重合且共线")
    elif nr == 6:
        print("6:完全重合")

    print("交点:" + str(intPoint))
